﻿using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;

namespace AlgorithmTest
{
    // T_[四个数字排序]_[算法名]
    public class T_0194_LongestUnivaluePath : IAlgorithm
    {
        // 687. 最长同值路径

        // 给定一个二叉树的 root ，返回 最长的路径的长度 ，这个路径中的 每个节点具有相同值 。 这条路径可以经过也可以不经过根节点。
        // 两个节点之间的路径长度 由它们之间的边数表示。

        // 提示:
        //   树的节点数的范围是[0, 10^4] 
        //   -1000 <= Node.val <= 1000
        //   树的深度将不超过 1000 

        public void Test()
        {
            // 算法参数定义
            var root = new TreeNode(1, new TreeNode(4, new TreeNode(4), new TreeNode(4)), new TreeNode(5, null, new TreeNode(5)));
            // 算法执行与打印
            Console.Write(LongestUnivaluePath(root));
        }

        // 算法
        // root = [5,4,5,1,1,5]
        public int LongestUnivaluePath(TreeNode root)
        {
            res = 0;
            DFS(root);
            return res;
        }
        int res;
        private int DFS(TreeNode root)
        {
            if (root == null) return 0;
            int left = DFS(root.left), right = DFS(root.right);
            int left1 = 0, right1 = 0;
            if (root.left != null && root.left.val == root.val)
            {
                left1 = left + 1;
            }
            if (root.right != null && root.right.val == root.val)
            {
                right1 = right + 1;
            }
            res = Math.Max(res, left1 + right1);
            return Math.Max(left1, right1);
        }
    }
}
